package cuiyt.algorithm.dfs;

import algorithm.TreeNode;
import org.apache.hadoop.hdfs.tools.DFSAdmin;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author cyt
 * @create 2020-08-24 14:20
 */
public class T112 {

    public static void main(String[] args) {
    }

    /**
     * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
     * <p>
     * 说明: 叶子节点是指没有子节点的节点。  SUM = 22
     * 5
     * / \
     * 4   8
     * /   / \
     * 11  13  4
     * /  \      \
     * 7    2      1
     *
     * @param root
     * @param sum
     * @return
     */


    public static boolean bfs(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<Integer> value = new LinkedList<Integer>();
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        /**
         * 加入根节点
         */
        value.offer(root.val);
        queNode.offer(root);
        /**
         *开始搜索
         */
        while (!queNode.isEmpty()) {
            /**
             * 取出队首判断结果
             */
            TreeNode poll = queNode.poll();
            Integer integer = value.poll();
            if (poll.left == null && poll.right == null) {
                if (sum == integer) {
                    return true;
                }
            }
            /**
             * 把下一层节点放入队首中， 等待后续搜索
             */
            if (poll.right != null) {
                value.offer(integer + poll.right.val);
                queNode.offer(poll.right);
            }
            if (poll.left != null) {
                value.offer(integer + poll.left.val);
                queNode.offer(poll.left);
            }
        }
        return false;
    }

    /**
     * 按照题意直接深搜， 题中要求： 从叶子节点到根节点的和，那么就可以演变成差来计算，在进行下一步搜索的时候可以直接左右子树同时搜索
     *
     * @param root
     * @param sum
     * @return
     */
    public static boolean dfs(TreeNode root, int sum) {
        /**
         * 特判
         */
        if (root == null) {
            return false;
        }
        /**
         * 结果对
         */
        if (root.val == sum && root.left == null && root.right == null) {
            return true;
        }
        /**
         * 下一步搜索
         */
        boolean left = dfs(root.left, sum - root.val);
        boolean right = dfs(root.right, sum - root.val);
        return right || left;
    }
}
